package com.zjsru.plan2024.normal;

/**
 * 检查数组是否存在有效划分
 * @Author: cookLee
 * @Date: 2024-03-03
 */
public class ValidPartition {

    /**
     * 主
     * \
     * 子数组 恰 由 2 个相等元素组成，例如，子数组 [2,2] 。
     * 子数组 恰 由 3 个相等元素组成，例如，子数组 [4,4,4] 。
     * 子数组 恰 由 3 个连续递增元素组成，并且相邻元素之间的差值为 1 。例如，子数组 [3,4,5] ，但是子数组 [1,3,5] 不符合要求。
     * \
     * 输入：nums = [4,4,4,5,6]
     * 输出：true
     * 解释：数组可以划分成子数组 [4,4] 和 [4,5,6] 。
     * 这是一种有效划分，所以返回 true 。
     * \
     * 输入：nums = [1,1,1,2]
     * 输出：false
     * 解释：该数组不存在有效划分。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        ValidPartition validPartition = new ValidPartition();
        int[] nums = new int[]{4,4,4,5,6};
        System.out.println(validPartition.validPartition(nums));
    }

    /**
     * 动态规划
     *
     * @param nums nums
     * @return boolean
     */
    public boolean validPartition(int[] nums) {
        int len = nums.length;
        boolean[] booleans = new boolean[len + 1];
        booleans[0] = true;
        //连续数字的校验
        for (int i = 1; i <= len; i++) {
            if(i >= 2){
                booleans[i] = booleans[i - 2] && this.valid2(nums[i - 1],nums[i - 2]);
            }
            if(i >= 3){
                booleans[i] = booleans[i] || booleans[i - 3] && this.valid3(nums[i - 1], nums[i - 2], nums[i - 3]);
            }
        }
        return booleans[len];
    }

    /**
     * 校验2个数字是否相等
     *
     * @param num1 num1
     * @param num2 num2
     * @return boolean
     */
    private boolean valid2(int num1, int num2) {
        return num1 == num2;
    }

    /**
     * 校验3个数字是否相等
     *
     * @param num1 num1
     * @param num2 num2
     * @param num3 num3
     * @return boolean
     */
    private boolean valid3(int num1, int num2, int num3) {
        return (num1 == num2 && num2 == num3) || (num3 + 2 == num2 + 1 && num2 + 1 == num1);
    }

}
